/**
 * 斐波那契数列（Fibonacci sequence）
 *
 * 斐波那契数（Fibonacci number）
 * ---------------------------------
 * 文档查看: /document/algo/fibonacci_sequence.md
 */

public class FibonacciSequence {
  public static long fib1(long n) {
    if (n < 2) return n;
    return fib1(n - 1) + fib1(n - 2);
  }

  public static long fib2(long n) {
    if (n < 0) return 0;
    if (n < 2) return n;
    long numPre = 0;
    long numNext = 1;
    long sum = 0;
    for (int i = 2; i <= n; i++) {
      sum = numPre + numNext;
      numPre = numNext;
      numNext = sum;
    }
    return numNext;
  }

  public static void main(String[] args) {
    // System.out.println(fib1(0));
    // System.out.println(fib1(1));
    // System.out.println(fib1(2));
    // System.out.println(fib1(3));

    // System.out.println(fib1(93));


    // System.out.println(fib2(0));
    // System.out.println(fib2(1));
    // System.out.println(fib2(2));
    // System.out.println(fib2(3));
    // System.out.println(fib2(4));

    // System.out.println(fib2(93));
  }
}